package hah;

import com.sun.tools.classfile.ConstantPool;
import sun.nio.cs.ext.MacHebrew;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;

public class hahaha66 {
    public boolean isHappy(int n) {
        int slow=n;
        int fast=n;
        do {
            slow=sum(slow);
            fast=sum(fast);
            fast=sum(fast);
        }while (slow!=fast);
        return fast==1;
    }
    public int sum(int n){
        int sum=0;
        while (n>0){
            int temp=n%10;
            sum+=temp*temp;
            n/=10;
        }
        return sum;
    }
    public boolean isPowerOfTwo(int n) {
            int flag=0;
            int p=1;
            while (n!=1){
                int temp=n&1;
                if (temp==1){
                    return false;
                }
            }
            return true;
    }
    //最长子序列    ----动态规划
    public int longestCommonSubsequence(String text1, String text2) {
        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();
        int t1l=t1.length;
        int t2l=t2.length;
        int[][] res=new int[t1l+1][t2l+1];
        int[][] route=new int[t1l+1][t2l+1];
        for (int j=0;j<t2l;j++)
            res[0][j]=0;
        for (int i=0;i<t1l;i++)
            res[i][0]=0;
        for (int m=1;m<t1l+1;m++){
            for (int n=1;n<t2l+1;n++){
                char c1=t1[m-1];
                char c2=t2[n-1];
                if (c1==c2){
                    res[m][n]=res[m-1][n-1]+1;
                    route[m][n]=1;
                }else if (res[m-1][n]>=res[m][n-1]){
                    res[m][n]=res[m-1][n];
                    route[m][n]=2;
                }else {
                    res[m][n]=res[m][n-1];
                    route[m][n]=3;
                }
            }
        }
        for (int i=0;i<t1l+1;i++){
            for (int j=0;j<t2l+1;j++){
                System.out.print(res[i][j]+" ");
            }
            System.out.println("  ");
        }
        System.out.println(" ");
        for (int i=0;i<t1l+1;i++){
            for (int j=0;j<t2l+1;j++){
                System.out.print(route[i][j]+" ");
            }
            System.out.println("  ");
        }
        return res[t1l][t2l];
    }
    private HashMap<Integer,Integer> map=new HashMap<>();
    public int numRabbits(int[] answers) {
        int len = answers.length;
        int sum = 0;
        if (len == 0)
            return 0;
        for (int i = 0; i < len; i++) {
            if (map.containsKey(answers[i])) {
                int val = map.get(answers[i]);
                int rval = val + 1;
                map.put(answers[i], rval);
            } else {
                map.put(answers[i], 1);
            }
        }
        Set<Integer> integers = map.keySet();
        for (Integer i : integers) {
            int val = map.get(i);
            if (i == 0) {
                sum += val;
            } else if (i >= val) {
                sum += i + 1;
            } else {
                if (i == 1) {
                    if (val % 2 == 0) {
                        sum += val;
                    } else {
                        int rval = val + 1;
                        sum += rval;
                    }
                } else {
                    int d = i + 1;
                    int k = val / d;
                    int z = val % d;
                    if (z == 0) {
                        sum += k * d;
                    } else {
                        sum += (k + 1) * d;
                    }
                }
            }
        }
        return sum;
    }
    public void merge(int[] nums1, int m, int[] nums2, int n) {
            for (int i=n;i<m;i++){
                nums1[i]=nums2[i-n];
            }
            Arrays.sort(nums1);
    }
    public int removeDuplicates(int[] nums) {
            int len=nums.length;
            if (len<=2)
                return len;
            int u=1;
            for (int i=2;i<len;i++){
                if (nums[i]!=nums[i-2]){
                    u++;
                    nums[u]=nums[i];
                }
            }
            return u;
    }

    public int findMin(int[] nums) {
            int low=0;
            int high=nums.length-1;
            while (nums[low]==nums[high])
                high--;
            while (low<high){
                int mid=(low+high)>>1;
                if (nums[mid]>nums[high]){
                    low=mid+1;
                }else {
                    high=mid;
                }
            }
            return nums[0]<nums[low]?nums[0]:nums[high];
    }
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int p1=m-1;
        int p2=n-1;
        for (int i=nums1.length-1;i>=0&&p1>-1&&p2>-1;i--){
            if (nums1[p1]>nums2[p2]){
                nums1[i]=nums1[p1];
                p1--;
            }else  if (nums1[p1]<nums2[p2]){
                nums1[i]=nums2[p2];
                p2--;
            }else {
                nums1[i]=nums1[p1];
                p1--;
            }
        }
        if (p2>=0){
            for (int i=0;i<=p2;i++){
                nums1[i]=nums2[p2];
            }
        }
    }
    public int nthUglyNumber(int n) {
            int[] res=new int[n+1];
            res[1]=1;
            int p1=1;int p2=1;int p3=1;
            for (int i=1;i<=n;i++){
                int num1=res[p1]*2;
                int num2=res[p2]*3;
                int num3=res[p3]*5;
                res[i]=Math.min(num1,Math.min(num2,num3));
                if (res[i]==num1){
                    p1++;
                }
                if (res[i]==num2){
                    p1++;
                }
                if (res[i]==num3){
                    p1++;
                }
            }
            return res[n];
    }
    /**public String largestNumber(int[] nums) {
            int maxbit=max(nums[0]);
            for (int i=1;i< nums.length;i++){
                maxbit= Math.max(max(nums[i]),maxbit);
            }
            int[] com=new int[nums.length];
            int[] flag=new int[nums.length];
            for (int i=0;i<com.length;i++){
                com[i]=nums[i];
            }
            for (int i=0;i<com.length;i++){
                while (max(com[i])<maxbit){
                    com[i]*=10;
                }
            }
            StringBuffer sb=new StringBuffer();
            while (contains(flag)){
                int index=maxIndex(com,flag,nums);
                sb.append(nums[index]);
                flag[index]=1;
            }
            return sb.toString();

    }
    public boolean contains(int[] flag){
        for (int i=0;i<flag.length;i++){
            if (flag[i]==0){
                return true;
            }
        }
        return false;
    }
    public int max(int i){
        int res=0;
        while (i!=0){
            res++;
            i=i/10;
        }
        return res;
    }
    public int maxIndex(int[] arr,int[] flag,int[] nums){
        int index=-1;
        int max=-1;
        for (int i=0;i<arr.length;i++){
            if (flag[i]==0) {
                if (arr[i] > max) {
                    max = arr[i];
                    index = i;
                } else if (arr[i] == max) {
                    if (nums[i] < nums[index]) {
                        index = i;
                    }
                }else{

                }
            }
        }
        return index;
    }**/


    public String largestNumber(int[] nums) {
        int n=nums.length;
        String[] ss=new String[n];
        for (int i=0;i<n;i++){
            ss[i]=""+nums[i];
        }

        //这段代码能懂，但自己写不出来，基础忘了啊！！需要复习一下！！
        Arrays.sort(ss,(a,b)->{
            String s1=a+b;
            String s2=b+a;
            return s2.compareTo(s1);
        });

        StringBuffer sb=new StringBuffer();
        for (String s:ss){
            sb.append(s);
        }
        int len=sb.length();
        int k=0;
        while (k<len-1&&sb.charAt(k)=='0'){
            k++;
        }
        return sb.substring(k);
    }

    /**
     * 最大子序列问题，自己用动态规划写的，但是超时了，淦！！！
    public int maxSubArray(int[] nums) {
        int[] max=new int[nums.length];
        max[0]=nums[0];
        int maxval=Integer.MIN_VALUE;
        for (int i=1;i<max.length;i++){
            if (nums[i]<=0&&max[i-1]>0){
                max[i]=max[i-1];
            }else if (nums[i]<0&&max[i-1]<0){
                max[i]=Math.max(max[i-1],nums[i]);
            }
            else {
                max[i]=Math.max(max[i-1],max(nums,i));
            }
        }
        return max[nums.length-1];
    }

    public int max(int[] nums,int k){
        int res =Integer.MIN_VALUE;

        for (int i=k;i>-1;i--){
            int temp=0;
            for (int j=i;j<=k;j++){
                temp+=nums[j];
            }
            res=Math.max(res,temp);
        }
        return res;
    }**/

    //最大子序列 别人的解法 感觉应该是贪心 好巧妙！！
    public int maxSubArray(int[] nums) {
        int sum=0;
        int ans=nums[0];
        for (Integer num:nums){
            if (sum>0){
                sum+=num;
            }else {
                sum=num;
            }
            ans=Math.max(ans,sum);
        }
        return ans;

    }
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            int len=nums.length;
            if (len==0)
                return false;
            for (int i=0;i<len;i++){
                for (int j=i+1;j<=i+k&&j<len;j++){
                    if (Math.abs(nums[i])-nums[j]<=t){
                        return true;
                    }
                }
            }
            return false;
    }


    public int strStr(String haystack, String needle) {
            int n=haystack.length();
            int m=needle.length();
            if (m==0){
                return 0;
            }
            int[] p=new int[m];
            for (int i=1,j=0;i<m;i++){
                while (j>0&&needle.charAt(j)!=needle.charAt(i)){
                    j=p[j-1];
                }
                if (needle.charAt(i)==needle.charAt(j)){
                    j++;
                }
                p[i]=j;
            }
            for (int i=0,j=0;i<n;i++){
                while (j>0&haystack.charAt(i)!=needle.charAt(j)){
                    j=p[j-1];
                }
                if (haystack.charAt(i)==needle.charAt(j)){
                    j++;
                }
                if (j==m){
                    return i-m+1;
                }
            }
            return -1;


    }
    public boolean judgeSquareSum(int c) {
        for(int i=0;i<=c;i++){
            if (isSquare(c-i*i)){
                return true;
            }
        }
        return false;
    }
    public boolean isSquare(int n){
        for (int i=1;i<=n/2;i++){
            if (i*i==n){
                return true;
            }
        }
        return false;
    }
    public int xorOperation(int n, int start) {
         int res=0;
         for (int i=0;i<n;i++){
             res^=(start+2*i);
         }
         return res;
    }
    public int[] decode(int[] encoded, int first) {
            int[] res=new int[encoded.length+1];
            res[0]=first;
            for (int i=1;i<res.length;i++){
                res[i]=res[i-1]^encoded[i-1];
            }
            return res;
    }

    public static void main(String[] args) {

    }
}

